// 19. 删除链表的倒数第 N 个结点
function ListNode(val) {
  this.val = val;
  this.next = null;
}

var removeNthFromEnd = function (head, n) {
  let dummy = new ListNode(-1)
  dummy.next = head
  // 要传dummy，才运行成功，不然22行报错 .next前是undefined ? ? ? ?
  let x = findFromEnd(dummy, n + 1)
  x.next = x.next.next
  return dummy.next
};

// 删除倒数第N个节点，首先找到倒数第N+1个节点
var findFromEnd = function (head, k) {
  let p1 = head
  let p2 = head

  for (let i = 0; i < k; i++) {
    p1 = p1.next
  }

  while (p1 !== null) {
    p1 = p1.next;
    p2 = p2.next;
  }

  return p2
}


var findFromEnd = function (head, k) {
  let p1 = head;
  let p2 = head;
  // p1 先走 k 步
  for (let i = 0; i < k; i++) {
    p1 = p1.next;
  }
  // p1 和 p2 同时走直到 p1 走到末尾
  while (p1 !== null) {
    p1 = p1.next;
    p2 = p2.next;
  }
  // 此时 p2 就是倒数第 k 个节点
  return p2;
};


/**
 这个逻辑就很简单了，要删除倒数第 n 个节点，就得获得倒数第 n + 1 个节点的引用，可以用我们实现的 findFromEnd 来操作。

不过注意我们又使用了虚拟头结点的技巧，也是为了防止出现空指针的情况，比如说链表总共有 5 个节点，题目就让你删除倒数第 5 个节点，也就是第一个节点，那按照算法逻辑，应该首先找到倒数第 6 个节点。但第一个节点前面已经没有节点了，这就会出错。

但有了我们虚拟节点 dummy 的存在，就避免了这个问题，能够对这种情况进行正确的删除。
 */
